package lib

func init() {
	Probs = append(Probs, Problem{
		Num:         934,
		Discription: " 在两个岛屿间修一座桥的最短距离",
		Level:       2,
		Labels: map[string]int{
			"图连通性": 1,
			"递归":   1,
		},
	})
}

//思路：
//1.先找出第一个岛的所有节点（第一个连通子图）
//2.找第二个岛的所有节点，每找到一个就遍历一遍第一个岛的所有节点更新最小曼哈顿距离
func ShortestBridge(grid [][]int) int {
	m := len(grid)
	n := len(grid[0])
	var array [][2]int
	var dfs func(int, int, int)
	dirs := [4][2]int{{1, 0}, {0, 1}, {-1, 0}, {0, -1}}
	res := m + n - 3

	dfs = func(i, j, k int) {
		if i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == 0 {
			return
		}

		if grid[i][j] == 1 {
			//找到岛后置0，避免成环
			grid[i][j] = 0
			if k == 0 {
				array = append(array, [2]int{i, j})
			} else {
				for _, pos := range array {
					res = min(res, abs(pos[0]-i)+abs(pos[1]-j)-1)
				}
			}

			for _, dir := range dirs {
				dfs(i+dir[0], j+dir[1], k)
			}

		}
	}

	island := 0
	for i := 0; i < len(grid); i++ {
		for j := 0; j < len(grid[0]); j++ {
			if grid[i][j] == 1 {
				dfs(i, j, island)
				island++
				if island == 2 {
					break
				}
			}
		}
		if island == 2 {
			break
		}
	}

	return res
}
